package me.project.offer;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

/**
 * 1->2->3
 * 3->2->1
 * 输入一个链表，从尾到头打印链表每个节点的值。
 *
 * @author Mcdull
 * @date 2018-6-29
 */
public class Solution06 {
    /**
     * AC  	19 ms 	9124K
     * 1：use stack
     * 2：递归
     * 3：
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (listNode == null){
            return list;
        }
        Stack<Integer> stack = new Stack<Integer>();
        while (listNode != null){
            stack.add(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }

    /**
     * AC   22 ms 	9384K
     *  Collections.reverse()
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (listNode == null){
            return list;
        }
        while (listNode != null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(list);
        return list;
    }

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}


